import java.util.*;
import java.io.*;
import java.math.*;
/*
求组合数 I
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C_a^b mod (10^9 + 7) 的值。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1 ≤ n ≤ 10000，
1 ≤ b ≤ a ≤ 2000

输入样例：
3
3 1
5 3
2 2

输出样例：
3
10
1
 */
//public class Main {
//    static int[][] c = new int[2001][2001];
//    static final int mod = (int) 1e9 + 7;
//
//    static void initCoefficients() {
//        for (int i = 0; i < 2001; i++) {
//            for (int j = 0; j <= i; j++) {
//                if (j == 0) c[i][j] = 1;
//                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
//            }
//        }
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        initCoefficients();
//        for (int i = 0; i < n; i++) {
//            System.out.println(c[sc.nextInt()][sc.nextInt()]);
//        }
//    }
//}

/*
求组合数 II
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 C_a^b mod (10^9 + 7) 的值。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1 ≤ n ≤ 10000，
1 ≤ b ≤ a ≤ 100000

输入样例：
3
3 1
5 3
2 2

输出样例：
3
10
1
 */
//C_a^b = a! / ((a-b)! * b!)
//public class Main {
//    static long[] fact = new long[100010];
//    static long[] inFact = new long[100010];
//    static final long mod = (long) 1e9 + 7;
//
//    static long quickPow(long a, long k, long p) {
//        long res = 1;
//        while (k > 0) {
//            if ((k & 1) == 1) res = res * a % p;
//            a = a * a % p;
//            k >>= 1;
//        }
//        return res;
//    }
//
//    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
//        int n = Integer.parseInt(br.readLine());
//        fact[0] = inFact[0] = 1;
//        for (int i = 1; i < 100010; i++) {
//            fact[i] = fact[i - 1] * i % mod;
//            inFact[i] = inFact[i - 1] * quickPow(i, mod - 2, mod) % mod;
//        }
//        for (int i = 0; i < n; i++) {
//            String[] s = br.readLine().split(" ");
//            int a = Integer.parseInt(s[0]);
//            int b = Integer.parseInt(s[1]);
//            pw.println(fact[a] * inFact[b] % mod * inFact[a - b] % mod);
//            pw.flush();
//        }
//    }
//}

/*
求组合数 III

给定 n 组询问，每组询问给定三个整数 a，b，p，其中 p 是质数，请你输出 C_b^a mod p 的值。

输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a，b，p。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1 ≤ n ≤ 20,
1 ≤ b ≤ a ≤ 10^18,
1 ≤ p ≤ 10^5

输入样例：
3
5 3 7
3 1 5
6 4 13

输出样例：
3
3
2
 */

/// /Lucas公式 C(a,b)(i.e.C_a^b)≡C(a%p,b%p)*C(a/p,b/p) (mod p)
//public class Main {
//    static long p;
//
//    static long quickPow(long a, long k)//第三个参数就是全局变量p
//    {
//        long res = 1;
//        while (k > 0) {
//            if ((k & 1) == 1) res = res * a % p;
//            k >>= 1;
//            a = a * a % p;
//        }
//        return res;
//    }
//
//    static long C(long a, long b) {
//        if (a < b) return 0;
//        long up = 1, down = 1;
//        for (long i = 1; i <= b; i++) down = down * i % p;
//        for (long i = a; i >= a - b + 1; i--) up = up * i % p;
//        return up * quickPow(down, p - 2) % p;
//    }
//
//    static long lucas(long a, long b) {
//        if (a < p && b < p) return C(a, b);
//        return lucas(a % p, b % p) * lucas(a / p, b / p) % p;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int n = sc.nextInt();
//        for (int i = 0; i < n; i++) {
//            long a = sc.nextLong(), b = sc.nextLong();
//            p = sc.nextLong();
//            System.out.println(lucas(a, b));
//        }
//    }
//}

/*
求组合数IV
输入两个整数 a 和 b，求组合数 C(a, b) 的值。注意结果可能很大，需要使用高精度计算。

输入格式
共一行，包含两个整数 a 和 b。

输出格式
共一行，输出 C(a, b) 的值。

数据范围
1 ≤ b ≤ a ≤ 5000

输入样例：
5 3

输出样例：
10
 */
//public class Main {
//    static int[] primes = new int[2000];
//    static boolean[] st = new boolean[2000];
//    static int cnt;
//    static int[] sum = new int[2000];
//
//    //线性筛法求质数
//    static void getPrimesLinear(int n) {
//        for (int i = 2; i <= n; i++) {
//            if (!st[i]) {
//                primes[cnt++] = i;
//            }
//            for (int j = 0; primes[j] <= n / i; j++) {
//                st[i * primes[j]] = true;
//                if (i % primes[j] == 0) break;
//            }
//        }
//    }
//
//    //计算a!中因子p的次数
//    static int getTimes(int a, int p) {
//        int res = 0;
//        while (a > 0) {
//            res += a / p;
//            a /= p;
//        }
//        return res;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int a = sc.nextInt(), b = sc.nextInt();
//        getPrimesLinear(a);
//        for (int i = 0; i < cnt; i++) {
//            int p = primes[i];
//            sum[i] = getTimes(a, p) - getTimes(b, p) - getTimes(a - b, p);
//        }
//        BigInteger res = new BigInteger("1");
//        for (int i = 0; i < cnt; i++) {
//            for (int j = 0; j < sum[i]; j++) {
//                res = res.multiply(BigInteger.valueOf(primes[i]));
//            }
//        }
//        System.out.println(res);
//    }
//}

/*
给定n个0和n个1，它们将按照某种顺序排成长度为2n的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中0的个数都不少于1的个数的序列有多少个。

输出的答案对10^9 + 7 取模。

输入格式
共一行，包含整数n。

输出格式
共一行，包含一个整数，表示答案。

数据范围
1 ≤ n ≤ 10^5

输入样例：
3

输出样例：
5
 */
//卡特兰数 = C(2n,n)-C(2n,n-1)= C(2n,n) / (n+1)
//public class Main {
//    static long n;
//    static final long mod = (long) 1e9 + 7;
//
//    static long quickPow(long a, long k, long p) {
//        long res = 1;
//        while (k > 0) {
//            if ((k & 1) == 1) res = res * a % p;
//            k >>= 1;
//            a = a * a % p;
//        }
//        return res;
//    }
//
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        n = sc.nextInt();
//        long res = 1;
//        for (long i = 2 * n; i >= n + 1; i--) res = res * i % mod;
//        for (long i = 1; i <= n; i++) res = res * quickPow(i, mod - 2, mod) % mod;
//        res = res * quickPow(n + 1, mod - 2, mod) % mod;
//        System.out.println(res);
//    }
//}

/*
给定一个整数n和m个不同的质数p1，p2，…，Pm。
请你求出1～n中能被p1，p2，…，pm中的至少一个数整除的整数有多少个。

输入格式
第一行包含整数n和m。
第二行包含m个质数。

输出格式
输出一个整数，表示满足条件的整数的个数。

数据范围
1≤m≤16，
1≤n，pi≤10^9

输入样例：
10 2
2 3

输出样例：
7
 */
public class Main {
    static long n, m;
    static long[] primes = new long[20];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        m = sc.nextLong();
        for (int i = 0; i < m; i++) primes[i] = sc.nextLong();
        long res = 0;
        for (int i = 1; i < 1 << m; i++) {
            long cnt = 0;//i二进制从右到左有几个1
            long t = 1;
            for (int j = 0; j < m; j++) {
                if ((i >> j & 1) == 1) {
                    ++cnt;
                    if (t * primes[j] > n) //表明n不可能有t * primes[j]这个因子（因为比n都大）
                    {
                        t = -1;
                        break;
                    }
                    t *= primes[j];
                }
                if (t != -1) {
                    if (cnt % 2 == 1) res += n / t;
                    else res -= n / t;
                }
            }
        }
        System.out.println(res);
    }
}